package com.lw.leetcode.arr.b;

import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * 120. 三角形最小路径和
 * 剑指 Offer II 100. 三角形中最小路径之和
 *
 * @author liw
 * @version 1.0
 * @date 2021/11/22 9:37
 */
public class MinimumTotal {
    public int minimumTotal(List<List<Integer>> triangle) {
        int size = triangle.size();

        if (size == 1) {
            return triangle.get(0).get(0);
        }

        int[] aa = new int[size];
        int bb;
        int cc;
        aa[0] = triangle.get(0).get(0);
        List<Integer> l2;

        for (int i = 1; i < size; i++) {
            l2 = triangle.get(i);
            bb = aa[0];
            aa[0] = l2.get(0) + bb;

            for (int j = 1; j < i; j++) {
                cc = aa[j];
                aa[j] = l2.get(j) + (Math.min(bb, aa[j]));
                bb = cc;
            }
            aa[i] = l2.get(i) + bb;
        }
        int max = aa[0];
        for (int i = 1; i < size; i++) {
            max = Math.min(max, aa[i]);
        }
        return max;
    }
}
